/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode *lcaDeepestLeaves(TreeNode *root)
    {
        unordered_map<TreeNode *, TreeNode *> fatherMap;
        unordered_map<int, vector<TreeNode *>> depthMap;
        int maxDepth = 0;
        setFatherAndDepth(root, 0, maxDepth, fatherMap, depthMap);
        auto &deepestNodes = depthMap[maxDepth];
        if (deepestNodes.size() == 1)
        {
            return deepestNodes[0];
        }
        unordered_set<TreeNode *> toSearchFathers(deepestNodes.begin(), deepestNodes.end());
        unordered_set<TreeNode *> fathers;
        while (true)
        {
            for (auto node : toSearchFathers)
            {
                fathers.insert(fatherMap[node]);
            }
            if (fathers.size() == 1)
            {
                return *fathers.begin();
            }
            else
            {
                toSearchFathers.clear();
                toSearchFathers.swap(fathers);
            }
        }
    }

    void setFatherAndDepth(TreeNode *tree, int depth, int &maxDepth,
                           unordered_map<TreeNode *, TreeNode *> &fatherMap,
                           unordered_map<int, vector<TreeNode *>> &depthMap)
    {
        // if(tree == nullptr) {return;}
        if (depthMap.find(depth) != depthMap.end())
        {
            depthMap[depth].push_back(tree);
        }
        else
        {
            depthMap[depth] = vector<TreeNode *>({tree});
        }
        if (depth > maxDepth)
        {
            maxDepth = depth;
        }
        if (tree->left != nullptr)
        {
            fatherMap.insert({tree->left, tree});
            setFatherAndDepth(tree->left, depth + 1, maxDepth, fatherMap, depthMap);
        }
        if (tree->right != nullptr)
        {
            fatherMap.insert({tree->right, tree});
            setFatherAndDepth(tree->right, depth + 1, maxDepth, fatherMap, depthMap);
        }
    }
};